#include <stdio.h>
#include <mpi.h>
#include <time.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include "sort.h"

double startTime, stopTime;
/*
 *  显示耗时
 */
void logCost(int id, const char *m)
{
    printf("进程%d: %s %f secs\n", id, m, (clock() - startTime) / CLOCKS_PER_SEC);
}

/**
 * @brief 打印数组
 *
 */
void logArr(int *v, int n, int id)
{
    int i;
    printf("进程 %d: ", id);
    for (i = 0; i < n; i++)
        printf("%d ", v[i]);
    printf("\n");
}

void printArray(int A[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

/**
 * @brief 合并有序数组
 *
 * @param v1
 * @param n1
 * @param v2
 * @param n2
 * @return int*
 */
int *merge(int *v1, int n1, int *v2, int n2)
{
    int i, j, k;
    int *result;

    result = (int *)malloc((n1 + n2) * sizeof(int));
    i = 0;
    j = 0;
    k = 0;
    while (i < n1 && j < n2)
    {
        if (v1[i] < v2[j])
        {
            result[k] = v1[i];
            i++;
            k++;
        }
        else
        {
            result[k] = v2[j];
            j++;
            k++;
        }
    }

    if (i == n1)
    {
        while (j < n2)
        {
            result[k] = v2[j];
            j++;
            k++;
        }
    }
    else
    {
        while (i < n1)
        {
            result[k] = v1[i];
            i++;
            k++;
        }
    }
    return result;
}

void beginSort(int *chunk, int s, const char* sortType) {
    //  选择排序，归并排序，快速排序，希尔排序，基数排序
    // selection merge quick shell radix
    if (strcmp("selection",sortType) == 0) {
       printf("选择排序\n"); 
       selection_sort(chunk, s); 
    }else if (strcmp("merge",sortType) == 0) {
       printf("归并排序\n"); 
       mergeSort(chunk, 0, s - 1);
    }else if (strcmp("quick",sortType) == 0) {
        printf("快速排序\n");
       quicksort(chunk, 0, s - 1);
    }else if (strcmp("shell",sortType) == 0) {
        printf("希尔排序\n");
       shell_sort(chunk, s);
    }else if (strcmp("radix",sortType) == 0) {
        printf("基数排序\n");
       radixsort(chunk, s);
    }
    // mergeSort(chunk, 0, s - 1);
    // quicksort(chunk, 0, s - 1);
    // shell_sort(chunk, s);
    // radixsort(chunk, s);
}

#define N 20

int main(int argc, char* argv[])
{
    int *data;
    int *chunk;
    int *other;
    int m, n = N;
    int id, p;
    int s;
    int i;
    int step;
    sscanf(argv[2],"%d",&n);
    char* sortType = argv[1];
    MPI_Status status;
    startTime = clock();
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &id);
    MPI_Comm_size(MPI_COMM_WORLD, &p);
    logCost(id, "MPI 设置完成");

    if (id == 0)
    {
        int r;
        srandom(clock());
        s = n / p;
        r = n % p;
        data = (int *)malloc((n + s - r) * sizeof(int));
        for (i = 0; i < n; i++)
            data[i] = random();
        if (r != 0)
        {
            for (i = n; i < n + s - r; i++)
                data[i] = 0;
            s = s + 1;
        }
        logCost(id, "生成随机数");
        MPI_Bcast(&s, 1, MPI_INT, 0, MPI_COMM_WORLD);
        chunk = (int *)malloc(s * sizeof(int));
        MPI_Scatter(data, s, MPI_INT, chunk, s, MPI_INT, 0, MPI_COMM_WORLD);
        logCost(id, "scattered data");
        // 排序
        beginSort(chunk, s, sortType);
        // logArr(chunk, s, id);
        logCost(id, "排序完成");
    } else {
        MPI_Bcast(&s, 1, MPI_INT, 0, MPI_COMM_WORLD);
        chunk = (int *)malloc(s * sizeof(int));
        MPI_Scatter(data, s, MPI_INT, chunk, s, MPI_INT, 0, MPI_COMM_WORLD);
        logCost(id, "获得数据");
        beginSort(chunk, s, sortType);
        // logArr(chunk, s, id);
        logCost(id, "排序完成");
    }

    // 合并数据
    step = 1;
    while (step < p)
    {
        if (id % (2 * step) == 0)
        {
            if (id + step < p)
            {
                MPI_Recv(&m, 1, MPI_INT, id + step, 0, MPI_COMM_WORLD, &status);
                other = (int *)malloc(m * sizeof(int));
                MPI_Recv(other, m, MPI_INT, id + step, 0, MPI_COMM_WORLD, &status);
                logCost(id, "获取需要合并的数据");
                chunk = merge(chunk, s, other, m);
                /*logArr(chunk, s, id); */
                logCost(id, "合并数据");
                s = s + m;
            }
        }
        else
        {
            int near = id - step;
            MPI_Send(&s, 1, MPI_INT, near, 0, MPI_COMM_WORLD);
            MPI_Send(chunk, s, MPI_INT, near, 0, MPI_COMM_WORLD);
            logCost(id, "sent merge data");
            break;
        }
        step = step * 2;
    }
    // root进程数据保存到文件
    if (id == 0) {
        FILE *fout;
        stopTime = clock();
        printf("%d; %d processors; %f secs\n", s, p, (stopTime - startTime) / CLOCKS_PER_SEC);
        logCost(id, "打开文件");       
        fout = fopen(argv[1], "w");
        for (i = 0; i < s; i++)
            fprintf(fout, "%d\n", chunk[i]);
        fclose(fout);
        logCost(id, "关闭文件");
    }
    MPI_Finalize();
}